The present disclosure is related to the generation of Huffman codes.
As is well-known, in Huffman coding, greater or longer code lengths are assigned to the less-frequently occurring symbols. Likewise, the two least frequently occurring symbols will have the same code length. See, for example, D. A. Huffman, xe2x80x9cA Method for the Construction of Minimumxe2x80x94Redundancy Codes,xe2x80x9d Proceedings of the IRE, Volume 40 No. 9, pages 1098 to 1101, 1952. As is well-known, Huffman codes of a set of symbols are generated based at least in part on the probability of occurrence of source symbols. A binary tree, commonly referred to as a xe2x80x9cHuffman Treexe2x80x9d is generated to extract the binary code and the code length. See, for example, D. A. Huffman, xe2x80x9cA Method for the Construction of Minimumxe2x80x94Redundancy Codes,xe2x80x9d Proceedings of the IRE, Volume 40 No. 9, pages 1098 to 1101, 1952. D. A. Huffman, in the aforementioned paper, describes the process this way:
List all possible symbols with their probabilities;
Find the two symbols with the smallest probabilities;
Replace these by a single set containing both symbols, whose probability is the sum of the individual probabilities;
Repeat until the list contains only one member.
This procedure produces a recursively structured set of sets, each of which contains exactly two members. It, therefore, may be represented as a binary tree (xe2x80x9cHuffman Treexe2x80x9d) with the symbols as the xe2x80x9cleaves.xe2x80x9d Then to form the code (xe2x80x9cHuffman Codexe2x80x9d) for any particular symbol: traverse the binary tree from the root to that symbol, recording xe2x80x9c0xe2x80x9d for a left branch and xe2x80x9c1xe2x80x9d for a right branch. In some circumstances, it may be desirable to constrain or limit the maximum length code for the set of symbols, although state of the art Huffman Tree and/or Huffman Code processes do not generally provide for this.